#include <iostream>
#include <vector>


#define PROCESSNUM 5
#define SOURCENUM  3

class Lab {
private:
    void init() {
        srand(time(nullptr));
        Check.resize(5, false);
        // 初始化资源矩阵
        for (int i = 0; i < SOURCENUM; i++) {
            int num = rand() % 10 + 1;
            Available.push_back(num);
        }
        // 初始化最大需求矩阵
        for (int i = 0; i  < PROCESSNUM; i++) {
            std::vector<int> needed;
            for (int j = 0; j < SOURCENUM; j++) {
                int num = rand() % Available[j] + 1;
                needed.push_back(num);
            }
            Max.emplace_back(needed);
        }
        
        std::vector<int> tmp_ava(Available);
        
        for (int i = 0; i < PROCESSNUM; i++) {
            std::vector<int> alloc;
            // 对当前资源进行分配，有50%的几率为0
            // 也有50%的记录1~Max[i][j]，前提是有资源的前提下
            // 所以对于剩下的50%几率为1~min(Max[i][j], tmp_ava[j])
            // 最后tmp_ava[j]还要减去分配出去的
            for (int j = 0; j < SOURCENUM; j++) {
                bool iszero = rand() % 2;
                if (iszero || tmp_ava[j] == 0) {
                    alloc.push_back(0);
                } else {
                    int num = 1 + rand() % std::min(Max[i][j], tmp_ava[j]);
                    tmp_ava[j] -= num;
                    alloc.push_back(num);
                }
            }
            Allocation.emplace_back(alloc);
        }

        Work = tmp_ava;

        for (int i = 0; i < PROCESSNUM; i++) {
            std::vector<int> needed;
            for (int j = 0; j < SOURCENUM; j++) 
                needed.push_back(Max[i][j] - Allocation[i][j]);
            Need.emplace_back(needed);
        }
    }

    void printInfo() {
        std::cout << "Initial available:" << std::endl;
        for (auto& num : Available)
            std::cout << num << " ";
        std::cout << "\n" << std::endl;
        
        std::cout << "Max:" << std::endl;
        for (int i = 0; i < PROCESSNUM; i++) {
            std::cout << "p" << i << ": ";
            for (auto& num : Max[i])
                std::cout << num << " ";
            std::cout << "\n";
        }
        std::cout << std::endl;

        std::cout << "Allocated:" << std::endl;
        for (int i = 0; i < PROCESSNUM; i++) {
            std::cout << "p" << i << ": ";
            for (auto& num : Allocation[i])
                std::cout << num << " ";
            std::cout << "\n";
        }
        std::cout << std::endl;

        std::cout << "Available:" << std::endl;
        for (auto& num : Work) 
            std::cout << num << " ";
        std::cout << "\n" << std::endl;

        std::cout << "Work:" << std::endl;
        for (auto& num : Work) 
            std::cout << num << " ";
        std::cout << "\n" << std::endl;
        
        std::cout << "Needed:" << std::endl;
        for (int i = 0; i < PROCESSNUM; i++) {
            std::cout << "p" << i << ": ";
            for (auto& num : Need[i])
                std::cout << num << " ";
            std::cout << "\n";
        }
        std::cout << std::endl;    
    }

    bool isAlloc(int i) {
        for (int j = 0; j < SOURCENUM; j++)
            if (Need[i][j] > Work[j])
                return false;
        return true;
    }

    bool isDepth() {
        for (auto check : Check)
            if (check == false)
                return false;
        return true;
    }

    bool dfs() {
        // 当资源全都回来之后且搜索深度达到最深处，则成功返回
        if (Work == Available && isDepth()) {
            return true;
        }
        for (int i = 0; i < PROCESSNUM; i++) {
            if (Check[i]) continue;
            if (isAlloc(i)) {
                Check[i] = true;
                for (int j = 0; j < SOURCENUM; j++)
                    Work[j] += Allocation[i][j];
                Sequence.push_back(i);
                SequenceArray.push_back(Work);
                if (dfs()) 
                    return true;
                SequenceArray.pop_back();
                Sequence.pop_back();
                Check[i] = false;
                for (int j = 0; j < SOURCENUM; j++)
                   Work[j] -= Allocation[i][j];
            }
        }
        return false;    
    }

    void outSequence() {
        std::cout << "Safe Sequence: ";
        for (auto num : Sequence)
            std::cout << "p" << num << " ";
        std::cout << "\n";

        printf("\tWork\n");
        for (int i = 0; i < PROCESSNUM; i++) {
            std::cout << "p" << Sequence[i] << "\t";
            for (auto num : SequenceArray[i])
                std::cout << num << " ";
            std::cout << "\n";
        }
    }
public:
    Lab() {
        init();
        printInfo();
    }

    void BankerAlgorithm() {
        // 先测试安全不安全
        // 深度搜索算法
        if (dfs()) {
            outSequence();
            // 根据当前的序列
        } else
            std::cout << "Deadlock!" << std::endl;
    }
private:
    std::vector<int> Available;
    std::vector<int> Work;
    std::vector<std::vector<int>> Max;
    std::vector<std::vector<int>> Allocation;
    std::vector<std::vector<int>> Need;
    std::vector<bool> Check;
    std::vector<int> Sequence;
    std::vector<std::vector<int>> SequenceArray;    
};

int main() {
    Lab lab;
    lab.BankerAlgorithm();
    return 0;
}